/*
 * @lc app=leetcode.cn id=301 lang=typescript
 *
 * [301] 删除无效的括号
 */

// @lc code=start
function removeInvalidParentheses(s: string): string[] {
  // 验证字符串是否是合法字符串
  const isValid = (str: string): boolean => {
    // 左括号数量
    let lcount = 0;
    for (let char of str) {
      if (char === '(') {
        lcount++;
      } else if (char === ')') {
        if (lcount === 0) return false;
        lcount--;
      }
    }
    return lcount === 0;
  };

  const ans: string[] = [];
  let currSet: Set<string> = new Set();
  currSet.add(s);
  while (true) {
    for (let str of currSet) {
      if (isValid(str)) ans.push(str);
    }
    // 找到答案，直接返回结果
    if (ans.length) return ans;

    // 去掉一个括号，进行下一次搜索
    const nextSet: Set<string> = new Set();
    for (let str of currSet) {
      for (let i = 0; i < str.length; i++) {
        // 连续相同的字符，只要处理一次即可
        if (i > 0 && str[i] === str[i - 1]) continue;
        if (str[i] === '(' || str[i] === ')') {
          // 增加下一次的搜索状态
          nextSet.add(str.substring(0, i) + str.substring(i + 1));
        }
      }
    }
    currSet = nextSet;
  }
}
// @lc code=end
